package com.cat.chapter048;

import java.util.Arrays;

/**
 * @author cat
 * @description https://leetcode.cn/problems/stamping-the-grid/
 * @create 2025/7/17 20:40
 * @since JDK17
 */

public class Solution03 {
    static int MAXN = 100010;
    static int[][] sum = new int[MAXN][MAXN];
    static int[][] diff = new int[MAXN][MAXN];

    // 二维前缀和用于判断是否可以贴邮票
    public boolean judge(int a, int b, int c, int d) {
        return sum[c][d] - sum[c][b - 1] - sum[a - 1][d] + sum[a - 1][b - 1] == 0;
    }

    public void add(int a, int b, int c, int d) {
        diff[a][b]++;
        diff[a][d + 1]--;
        diff[c + 1][b]--;
        diff[c + 1][d + 1]++;
    }

    public boolean possibleToStamp(int[][] grid, int h, int w) {
        int n = grid.length, m = grid[0].length;
        // 二维前缀和, 平移一次
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + grid[i - 1][j - 1];
            }
        }

        for (int i = 1; i <= n - h; i++) {
            for (int j = 1; j <= m - w; j++) {
                if (judge(i, j, i + h, j + w)) { // 该区域内没有1, 可以贴邮票
                    add(i, j, i + h, j + w);    // 开始贴邮票
                }
            }
        }
        // 做一次前缀和
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (diff[i][j] == 0 && grid[i - 1][j - 1] == 0) {
                    return false;
                }
            }
        }


        for (int i = 0; i <= n; i++) {
            Arrays.fill(sum[i], 0);
        }
        return true;
    }

}
